/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/triangle-count
   @Language: C++
   @Datetime: 19-05-09 16:22
   */

class Solution {
public:
	/**
	 * @param S: A list of integers
	 * @return: An integer
	 */
	int triangleCount(vector<int> &S) {
		// write your code here
		sort(S.begin(),S.end());
		int count=0;
		for(int i=2; i<S.size(); ++i){
			for(int j=0, k=i-1; j<k;){
				if(S[j]+S[k]>S[i]){
					count += k-j;
					--k;
				}
				else ++j;
			}
		}
		return count;
	}
};
